package org.shj.algorithm.string;

import java.util.Stack;

/**
 * 最长公共子序列问题： 两个序列 X 和 Y ， 其公共子序列中长度最长的子序列
 * 子序列定义： 一个序列 S，任意删除 N 个字符得到序列 T，则 T 为 S 的子序列
 * 例如： 两个序列 13455 与 245576，其最长公共子序列是：  455
 *       两个序列 acdfg 与 adfc，其最长公共子序列是：  adf
 *  注意： 并不要求连续
 *
 * 相关应用： 求两篇文章的相似度、DNA 的相似度
 *
 * 解题思路：
 * 1. 假设字符串 X，长度为 m, 字符串 Y，长度为 n
 * 2. 设 Ai = <X1, ..., Xm>，即 Ai 为 X 序列中前 i 项序列
 *   同样 Bj = <Y1, ..., Yn>
 * 3. 若 X 和 Y的结尾字符相等，则 LCS(X, Y) = LCS(Xm-1, Yn-1) + X[m]
 *   举例：  X = B D C A B A
 *          Y = A B C B D A
 *   则：LCS(X, Y) = LCS(BDCAB, ABCBD) + 'A'
 * 4. 若 X 和 Y 的结尾字符不相等，则 LCS(X, Y) 等于 LCS(Xm-1, Y) 和 LCS(X, Ym-1) 中的较大值
 *
 * 图见： LCS.png
 * @date 2019-01-22 12:03
 */
public class LongestCommonSubsequence {

    public static void main(String[] args){
        String a = "acdfge";
        String b = "adfce";

        String lcs = getLCS(a, b);
        System.out.println(lcs);

        dongGuiLCS(a,b);
    }

    private static String getLCS(String a, String b){
        int aLen = a.length();
        int bLen = b.length();

        if(aLen == 0 || bLen == 0){
            return "";
        }

        if(a.charAt(aLen - 1) == b.charAt(bLen - 1)){
            if(aLen == 1){
                return a;
            }
            if(bLen == 1){
                return b;
            }
            return getLCS(a.substring(0, aLen - 1), b.substring(0, bLen - 1)) + a.charAt(aLen - 1);
        }


        String lcsOne = getLCS(a.substring(0, aLen - 1), b);
        String lcsTwo = getLCS(a, b.substring(0, bLen - 1));

        return lcsOne.length() > lcsTwo.length() ? lcsOne : lcsTwo;
    }

    public static void dongGuiLCS(String a, String b){
        Store[][] arr = new Store[a.length() + 1][b.length() + 1];
        for(int i = 0; i <= a.length(); i++){
            Store s = new Store();
            s.setLcs(0);
            arr[i][0] = s;
        }

        for(int j = 0; j <= b.length(); j++){
            Store s = new Store();
            s.setLcs(0);
            arr[0][j] = s;
        }

        for(int i = 1; i <= a.length(); i++){
            for(int j = 1; j <= b.length(); j++){
                int left = arr[i][j-1].getLcs(); // 左边
                int up = arr[i-1][j].getLcs();
                int leftUp = arr[i-1][j-1].getLcs(); // 左上角

                Store s = new Store();
                if(a.charAt(i - 1) == b.charAt(j - 1)){
                    s.setDir("LU");
                    s.setLcs(leftUp + 1);
                }else{
                    int max = left > up ? left : up;
                    String dir = left > up ? "L" : "U";
                    s.setDir(dir);
                    s.setLcs(max);
                }
                arr[i][j] = s;
            }
        }

        Stack<String> chars = new Stack<>();
        int i = a.length();
        int j = b.length();
        while(j > 0 && i > 0){
            String dir = arr[i][j].getDir();
            if("LU".equals(dir)){
                chars.push(b.substring(j-1, j));
                i--;
                j--;
            }else if("L".equals(dir)){
                j--;
            }else{
                i--;
            }
        }

        while (!chars.empty()){
            System.out.print(chars.pop() + ", ");
        }
    }
}

class Store{
    private int lcs;
    /**
     * 方向，指示值从哪个位置得来。参见 LCS.png 图中的箭头
     */
    private String dir;

    public int getLcs() {
        return lcs;
    }

    public void setLcs(int lcs) {
        this.lcs = lcs;
    }

    public String getDir() {
        return dir;
    }

    public void setDir(String dir) {
        this.dir = dir;
    }
}
